/*
https://leetcode-cn.com/problems/find-the-shortest-superstring/solution/zui-duan-chao-ji-chuan-by-leetcode/
 */
import java.util.Arrays;

public class Solution943 {
    public String shortestSuperstring(String[] words) {
        int[][] f=new int[words.length][words.length];
        for (int i=0;i<words.length;i++){
            for (int j=0;j<words.length;j++){
                for (int k=Math.min(words[i].length(),words[j].length())-1;k>0;k--){
                    boolean flag=true;
                    for (int l=0;l<k;l++){
                        if (words[i].charAt(words[i].length()-k+l)!=words[j].charAt(l)){
                            flag=false;
                            break;
                        }
                    }
                    if (flag){
                        f[i][j]=k;
                        break;
                    }
                }
            }
        }
        int[][] dp=new int[1<<words.length][words.length];
        int[][] parent=new int[1<<words.length][words.length];
        for (int i=0;i<dp.length;i++){
            Arrays.fill(dp[i],Integer.MAX_VALUE);
        }
        for (int i=0;i<words.length;i++){
            dp[1<<i][i]=words[i].length();
            parent[1<<i][i]=-1;
        }
        for (int i=0;i<1<<words.length;i++){
            if (Integer.bitCount(i)>=2){
                for (int j=0;j<words.length;j++){
                    if ((i&(1<<j))>0){
                        for (int k=0;k<words.length;k++){
                            if ((i&(1<<k))>0 && j!=k && dp[i][j]>dp[i&(~(1<<j))][k]+words[j].length()-f[k][j]){
                                dp[i][j]=dp[i&(~(1<<j))][k]+words[j].length()-f[k][j];
                                parent[i][j]=k;
                            }
                        }
                    }
                }
            }
        }
        int ans=Integer.MAX_VALUE,pos=-1;
        for (int i=0;i<words.length;i++){
            if (dp[(1<<words.length)-1][i]<ans){
                ans=dp[(1<<words.length)-1][i];
                pos=i;
            }
        }
        StringBuilder stringBuilder=new StringBuilder();
        stringBuilder.append(words[pos]);
        int cur=(1<<words.length)-1;
        for (int i=0;i<words.length-1;i++){
            int t=cur,p=pos;
            cur=cur&(~(1<<pos));
            pos=parent[t][pos];
            stringBuilder.insert(0,words[pos].substring(0,words[pos].length()-f[pos][p]));
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        System.out.println(new Solution943().shortestSuperstring(new String[]{"catg","ctaagt","gcta","ttca","atgcatc"}));
    }
}
